package Backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @description: 组合总和
 * @author: w_jingbo
 * @date: 2023/9/7
 * @Copyright: 博客：http://coisini.wang
 */
public class combination {

    public static void main(String[] args) {

    }

    //组合总和三 https://leetcode.cn/problems/combination-sum-iii/description/
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(1,k,path,n,res) ;
        return res;
    }

    public void dfs(int begin ,int k , List<Integer> path , int  target , List<List<Integer>> res){
        if(target == 0 && path.size() == k){
            res.add(new ArrayList<>(path));
            return ;
        }
        for(int i = begin ; i < 10 ; i++){
            // 剪枝
            if(target - i < 0) return ;

            path.add(i) ;

            dfs(i+1,k,path,target - i , res) ;

            path.remove(path.size()-1);
        }
    }

    // 组合总和一 https://leetcode.cn/problems/combination-sum/submissions/
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        List<Integer> path = new ArrayList<>();
        process(candidates,res,path,target,0);
        return res;
    }

    public void process(int[] candidates , List<List<Integer>> res , List<Integer> path , int target, int index){
        if(target == 0){
            res.add(new ArrayList<>(path));
            return ;
        }
        for(int i = index ; i < candidates.length ; i++){
            if(candidates[i] > target){
                break;
            }

            path.add(candidates[i]);
            process(candidates,res,path,target - candidates[i],i);
            path.remove(path.size() - 1);
        }
    }

    //组合总和二 https://leetcode.cn/problems/combination-sum-ii/description/
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates,0,target,res,path);
        return res;
    }

    public void dfs(int[] candidates,int begin , int target ,List<List<Integer>> res,List<Integer> path){
        if(target == 0){
            res.add(new ArrayList<>(path));
            return ;
        }

        for(int i = begin ; i < candidates.length ; i++){
            if(target - candidates[i] < 0) {
                return ;
            }

            // 去重操作，因为candidates数组有重复数字，导致有重复
            if(i > begin && candidates[i] == candidates[i-1]){
                continue;
            }
            path.add(candidates[i]);
            dfs(candidates,i+1,target - candidates[i] , res , path) ;
            path.remove(path.size()-1);
        }
    }



}
